//
// Created by Haonan Xiong on 3/13/22.
//

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cstring>

using namespace std;

// Maximum size of the array
static const int MAX_LENGTH = 1000000;

// Generate an array of random integers
int *genRandomArray(int size) {
    static int array[MAX_LENGTH];
    srand((unsigned int) (time(nullptr)));
    for (int i = 0; i < size; i++) {
        array[i] = rand() % size;
    }
    return array;
}

// Print array
void printArray(const int array[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", array[i]);
    }
    printf("\n");
}

// Check if the array is sorted
bool isSorted(const int array[], int size) {
    for (int i = 1; i < size; i++) {
        if (array[i] < array[i - 1]) {
            return false;
        }
    }
    return true;
}

// Bubble sort
int *bubbleSort(int array[], int size) {
    for (int i = 0; i < size; i++) {
        for (int j = 0; j < size - 1 - i; j++) {
            if (array[j] > array[j + 1]) {
                swap(array[j], array[j + 1]);
            }
        }
    }
    return array;
}

// Insertion sort
int *insertionSort(int array[], int size) {
    for (int i = 1; i < size; i++) {
        int j = i;
        while (j > 0 && array[j] < array[j - 1]) {
            swap(array[j], array[j - 1]);
            j--;
        }
    }
    return array;
}

// Merge sort
int *mergeSort(int array[], int size) {
    if (size <= 1) {
        return array;
    }
    int mid = size / 2;
    int *left = new int[mid];
    int *right = new int[size - mid];
    for (int i = 0; i < mid; i++) {
        left[i] = array[i];
    }
    for (int i = mid; i < size; i++) {
        right[i - mid] = array[i];
    }
    mergeSort(left, mid);
    mergeSort(right, size - mid);
    int i = 0, j = 0, k = 0;
    while (i < mid && j < size - mid) {
        if (left[i] < right[j]) {
            array[k++] = left[i++];
        } else {
            array[k++] = right[j++];
        }
    }
    while (i < mid) {
        array[k++] = left[i++];
    }
    while (j < size - mid) {
        array[k++] = right[j++];
    }
    return array;
}

// Quick sort
int *quickSort(int array[], int size) {
    if (size <= 1) {
        return array;
    }
    int pivot = array[0];
    int i = 1, j = size - 1;
    while (i <= j) {
        while (i <= j && array[i] < pivot) {
            i++;
        }
        while (i <= j && array[j] > pivot) {
            j--;
        }
        if (i <= j) {
            swap(array[i], array[j]);
            i++;
            j--;
        }
    }
    array[0] = array[j];
    array[j] = pivot;
    quickSort(array, j);
    quickSort(array + j + 1, size - j - 1);
    return array;
}

int main() {
    int cases[6] = {10, 100, 1000, 10000, 100000, 1000000};
    // Iterate through each case
    for (int c = 0; c < 1; c++) {
        int size = cases[c];
        // Generate an array with random integers
        int *array = genRandomArray(size);
        int array1[MAX_LENGTH];

        printf("Array size: %d\n", size);

        // Copy generated array to a new array
        // And use different sorting algorithms
        // Check if the array is sorted
        // Print the time cost
        memcpy(array1, array, size * sizeof(int));
        clock_t start = clock();
        bubbleSort(array1, size);
        clock_t end = clock();
        if (isSorted(array1, size)) {
            printf("Bubble sort: %.3f ms\n", (double) (end - start) / CLOCKS_PER_SEC * 1000);
        }

        memcpy(array1, array, size * sizeof(int));
        start = clock();
        insertionSort(array1, size);
        end = clock();
        if (isSorted(array1, size)) {
            printf("Insertion sort: %.3f ms\n", (double) (end - start) / CLOCKS_PER_SEC * 1000);
        }

        memcpy(array1, array, size * sizeof(int));
        start = clock();
        mergeSort(array1, size);
        end = clock();
        if (isSorted(array1, size)) {
            printf("Merge sort: %.3f ms\n", (double) (end - start) / CLOCKS_PER_SEC * 1000);
        }


        memcpy(array1, array, size * sizeof(int));
        start = clock();
        quickSort(array1, size);
        end = clock();
        if (isSorted(array1, size)) {
            printf("Quick sort: %.3f ms\n", (double) (end - start) / CLOCKS_PER_SEC * 1000);
        }

        printf("\n");
    }
    return 0;
}
